//https://zhuanlan.zhihu.com/p/104386712
//https://leetcode.cn/problems/generate-parentheses/description/?envType=study-plan-v2&envId=top-100-liked
//数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
//n=3,["((()))","(()())","(())()","()(())","()()()"]
//n=1,["()"]

#include <string>
#include <vector>
#include <set>
#include <iostream>

using namespace std;

class Solution { 
public:
    std::vector<string> res{};
    void dfs(string cur_str,int left,int right,int n){
        if(left>n||right>n){
            return;
        }
        if(left<right){
            return;
        }
        if(left==n&&right==n){
            res.emplace_back(cur_str);
            std::cout << cur_str << std::endl;
        }
        dfs(cur_str+'(',left+1,right,n);
        dfs(cur_str+')',left,right+1,n);
    }
    vector<string> generateParenthesis(int n) {
        if(n<1) return res;
        dfs("",0,0,n);
        return res;
    };
};

class Solution { 
    public:
    std::vector<string> res{};
    void dfs(std::vector<char>& left_char,std::vector<char>& right_char,int left,int right,std::string str){
        
        if(left ==left_char.size() && right==right_char.size()){
            res.emplace_back(str);
            cout <<str << endl;
            return;
        }
        if(left >left_char.size()|| right>right_char.size()){
            return;
        }
        if(left<right){
            return;
        }
        std::string cur_left_string=str+"(";
        dfs(left_char,right_char,left+1,right,cur_left_string);
        std::string cur_right_string=str+")";
        dfs(left_char,right_char,left,right+1,cur_right_string);
    }
    vector<string> generateParenthesis(int n) {
        std::vector<char> left_char(n,'(');
        std::vector<char> right_char(n,')');
        dfs(left_char,right_char,0,0,"");
        return res;
    }
};